package com.company.ljh.medium;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @description:
 * 547. 省份数量
 * 中等
 * 1K
 * 相关企业
 * 有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
 *
 * 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
 *
 * 给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
 *
 * 返回矩阵中 省份 的数量。
 * @projectName:leet_code
 * @see:com.company.ljh.medium
 * @author:ljh
 * @createTime:2023/7/5 16:15
 * @version:1.0
 */
public class 省份数量 {
    public int findCircleNum(int[][] isConnected) {
        int circelNum = 0;;
        boolean isVisit[] = new boolean[isConnected.length];
        for(int i =0;i<isConnected.length;i++){
            if(!isVisit[i]){
                circelNum++;
                Queue<Integer>queue = new LinkedList();
                queue.offer(i);
                while(!queue.isEmpty()){
                    Integer item = queue.poll();
                    isVisit[item] = true;
                    //将该节点所有未访问关联节点放置到队列
                    for(int j=i+1;j<isConnected[0].length;j++){
                        if(isConnected[item][j] == 1&&!isVisit[j]){
                            queue.add(j);
                            isVisit[j] = true;
                        }
                    }
                }
            }
        }
        return circelNum;
    }

}
